A. Field of the Invention
The present invention relates generally to a graphic system for a personal computer. More particularly, the present invention relates to rendering polygons on a computer screen. Still more particularly, the present invention relates to a technique for dithering polygons to create curved surfaces.
B. Background of the Invention
Before the availability of the personal computer (PC), computer graphics packages were expensive tools primarily reserved for industrial applications. Early microcomputers were only capable of rendering simple line drawings with a low screen resolution (256.times.256, for example).
As microcomputers evolved, higher resolution color displays became available, and software applications routinely provided data output in a graphical format. The graphics techniques used were unstructured, with objects defined in terms of absolute coordinates using straight lines. Subsequently, graphics "primitives" were developed, enabling circles, ellipses, rectangles and polygons to be drawn with single software instructions. The use of primitives for drawing shapes increased the speed at which the images can be rendered.
The availability of computer graphics has generated a demand for higher resolutions and three dimensional (3-D) rendering capabilities. Computer animation and games, in particular, have spawned a revolution in computer graphics capabilities. A 3-D image can be represented in a computer system as a collection of graphical objects, such as polygons, lines, and points. A set of vertex points defines a polygon. Associated with each point are certain parameters, such as shading, texturing, color, and the like. Identification of other non-vertex points within the polygon typically is done through the use of linear interpolation. Once interpolated, the polygon can be rendered on a computer monitor by successive scanning of successive rows of the polygon.
Demand for higher performance computer graphics has led to graphics systems capable of much greater speed, resolution, and quality than graphics systems of only a few years ago. Traditionally, graphic systems employed an "8-8-8" standard, and many still do, in which eight bits are used to represent each of the three primary colors red, green, and blue. That is, eight bits are used for red, eight bits for green, and eight bits for blue. In an 8-8-8 system, therefore, twenty-four bits are needed to fully represent the color of a single pixel. Using eight bits for each color allows 256 different shades of each of the three primary colors. To increase the resolution of the color system, each color is represented with an "8.16" interpolator value in which sixteen bits of fractional color are included with each eight bit integer shade. With such resolution 8-8-8 graphics systems typically produce very high quality color images.
The down side of an 8-8-8 graphics system is that twenty-four bits are necessary to represent the integer color shade of a single pixel. The number of pixels on a typical computer screen today commonly approaches 1,000,000. With twenty-four bits of color and other parameters associated with each pixel, voluminous bits of information necessarily must be processed, thereby creating a demand for higher memory capacity and faster processing. Semiconductor part manufacturers have responded by developing higher performance graphics hardware. In many graphics applications, however, there is a demand for even higher performance from computer hardware.
Designers of graphics systems, therefore, have developed various techniques to achieve greater performance given the performance limitations of the supporting graphics hardware. For example, other graphics standards exist besides the 8-8-8 standard. One such standard is the "5-6-5" system in which five bits are used to represent shades of red, six bits are used to represent green, and five bits are used for blue. As shown in FIG. 1, in an eight bit system, eight bits are used to represent the color red. In a 5-6-5 system, however, only the upper or most significant five bits, i.e., bits R.sub.3 -R.sub.7, are used for red. The least significant three bits, R.sub.0 -R.sub.2, are simply truncated and not used. For the color green the upper six bits are used, i.e., G.sub.2 -G.sub.7, with bits G.sub.0 and G.sub.1 truncated. An extra bit is used for the color green because most human eyes are less sensitive to the color green and thus, additional resolution or precision for the color green is needed. The sixteen color bits that are used (five each for red and blue and six for green) are packed together for storage and/or processing. Other standards such as the "5-5-5" and "3-3-2" standards are also used.
Using a 5-6-5 system, instead of 8-8-8, advantageously allows the integer portions of the color representation to be stored in sixteen bits (i.e., two bytes) of memory instead of twenty-four bits (three bytes) as necessary for an 8-8-8 system. Moreover, significantly less memory is necessary to store computer images with a 5-6-5 system and more graphics information can be processed faster using existing hardware devices.
As one of ordinary skill in the art will recognize, representing a color shade with eight bits allows 2.sup.8 or 256 different integer shades of that color. Representing a color shade with only five bits, however, allows for just 2.sup.5 or 32 shades of that color and using six bits allows for 64 (2.sup.6) color shades. Referring now to FIG. 2, a comparison between an eight bit color standard and a five bit standard emphasizes the lower precision of a five bit system. Because the least significant three bits (bits 0-2) are truncated from an eight bit shade to create the five bit shade, eight bit color shades 0000 0000 through 0000 0111 (decimal 0-7) are represented by 00000 in the five bit system. In other words, with only five bits, the five bit representation cannot distinguish between eight bit shades 0-7 (decimal). Similarly, eight bit color shades 0000 1000 through 0000 1111 (decimal 8-15) are represented by 00001 in the five bit standard. This comparison illustrates that for every increment (or decrement) in a five bit color shade, eight eight-bit color shades are skipped. A similar comparison could be made for the six bit representation for the color green highlighting that because only the least significant two bits are truncated, there are four eight-bit green color shades for every six bit shade.
Polygons typically are drawn one row of pixels at a time, rendering pixels individually from one edge of the polygon to the other. To give the appearance of a curved surface to create 3-D images, a graphics system applies varying shades of color to the pixels rendered. For example, a polygon might be rendered with a dull shade of red on the left side of the polygon and bright red on the right side with a transition between the dull and bright shades for the intervening pixels. In an 8-8-8 system, with 256 integer shades each for red, green, and blue and sixteen bits of fractional shades, there is sufficient color precision to make the transitions of color across a polygon appear smooth to the human eye.
The attendant lower precision in a 5-6-5 graphics system does not permit color transitions across a polygon that are as smooth as in 8-8-8 systems. This problem is called "banding." Banding is caused by color transitions across polygons that include more pronounced, larger increments in shades of color because there are fewer different shades possible than in an 8-8-8 system. The boundary lines between different shades is more perceptible to the eye. A polygon rendered using the 5-6-5 color standard appears as bands of different shades of color on the computer screen rather than smooth transitions. Transitions in color shades in a 5-6-5 system between bands is noticeable despite the difference between adjacent bands of only a single shade of color.
To minimize the undesirable appearance of an image suffering from banding, the technique of dithering is used. Dithering takes advantage of the insufficient resolving ability of the human eye to distinguish individual pixels from a large group of pixels on a computer screen. Dithering allows the appearance of a color band to be altered to make the color shade of the band appear closer to the shade of an adjacent band, thereby smoothing the sharp transitions between the two bands. Graphics systems implementing known dithering techniques increment by one binary value randomly selected pixels in a band. Thus, some pixels in the dithered band are rendered using one shade of color, while other randomly selected pixels in the band are rendered using the color shade of the pixels in the adjacent band. The appearance of the dithered band thus appears closer to the shade of the adjacent band and the transition in color shades between the two bands is less noticeable to the eye. For the colors red and blue in a 5-6-5 system, incrementing a color shade by one shade level is equivalent to an increment of eight color shades in an eight bit system as demonstrated in FIG. 2. For the color green, a unitary increment equates to an increment of four shades of green in an eight bit system.
Although images using the dithering technique appear to lose the undesirable sharp edges between color bands, the result is still less than completely satisfactory because the dithered image is not an accurate rendition of the desired color transitions across the polygon. Because pixels are rendered randomly using one of two shades of color, the appearance to the eye of the band changes, but the resulting appearance is not necessarily the desired shade. Referring to FIG. 2, for example, if the desired eight bit red color shade in a particular region of a polygon is 0000 0010, commonly known dithering techniques will randomly render the pixels in that region with five bit shades 00000 and 00001. If, however, eight bit shade 0000 0111 were desired, systems implementing dithering will also randomly render the same group of pixels with five bit shades 00000 and 00001. The appearance to the eye will be the same because the same five bit shades (00000 and 00001) would be used in random fashion in both instances.
Thus, it would be desirable to provide a computer graphics system that solves the banding problem associated with graphics systems that represent color with fewer than eight bits of precision. In particular, it would be desirable to provide a graphics system in which fewer than eight bits are used to represent shades of color that can achieve the color precision of eight bit systems. Despite the advantages of such a system, to date, no such system has been developed.